package com.cqs.leetcode.backtrack;

import java.util.*;

/**
 * @author lixqw
 * @date 2020/9/9
 */
public class CombinationSumII40 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> list = new ArrayList<>();
        combination(candidates, target, 0, new ArrayList<>(), list);
        return list;
    }

    /**
     * @param candidates
     * @param target
     * @param level
     * @param tmp
     * @param result
     */
    private void combination(int[] candidates, int target, int level, List<Integer> tmp, List<List<Integer>> result) {
        //终止条件
        if (target == 0) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = level; i < candidates.length; i++) {
            //剪枝
            if ( target < candidates[i] || target < 0) return;
            //去重
            if (i > level && candidates[i] == candidates[i - 1]) {
                continue;
            }
            tmp.add(candidates[i]);
            combination(candidates, target - candidates[i],  i + 1, tmp, result);
            //回溯
            tmp.remove(tmp.size() - 1);
        }
    }

    static class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> list = new ArrayList<>();
            //求和
            int total = Arrays.stream(candidates).sum();
            combination(candidates, target, total, 0, new ArrayList<>(), list);
            return list;
        }

        /**
         * @param candidates
         * @param target
         * @param total      　剩余元素的和，用于剪枝
         * @param level
         * @param tmp
         * @param result
         */
        private void combination(int[] candidates, int target, int total, int level, List<Integer> tmp, List<List<Integer>> result) {
            if (target == 0) {
                result.add(new ArrayList<>(tmp));
                return;
            }
            //剪枝
            if (level >= candidates.length || target > total || target < 0) {
                return;
            }
            // 放或者不放

            //使用candidates[level]
            tmp.add(candidates[level]);
            combination(candidates, target - candidates[level], total - candidates[level], level + 1, tmp, result);
            //回溯
            tmp.remove(tmp.size() - 1);

            //不用candidates[level]
            //去重 －－－"同一层"的不要使用相同的元素 如[1,1,3]的情况，不去重的话就会有[1,3],[1,3]
            while (level < candidates.length - 1 && candidates[level] == candidates[level + 1]) level++;
            if (target <= total - candidates[level]) {
                combination(candidates, target, total - candidates[level], level + 1, tmp, result);
            }

        }
    }

    public static void main(String[] args) {
        Map<int[], Integer> tests = new LinkedHashMap<>();
        tests.put(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
        tests.put(new int[]{1, 1, 1}, 1);
        tests.put(new int[]{1, 1, 2}, 2);
        tests.put(new int[]{14, 6, 25, 9, 30, 20, 33, 34, 28, 30, 16, 12, 31, 9, 9, 12, 34, 16, 25, 32, 8, 7, 30, 12, 33, 20, 21, 29, 24, 17, 27, 34, 11, 17, 30, 6, 32, 21, 27, 17, 16, 8, 24, 12, 12, 28, 11, 33, 10, 32, 22, 13, 34, 18, 12}, 27);
        tests.put(new int[]{5}, 5);
        CombinationSumII40 com = new CombinationSumII40();
        Solution solution = new Solution();
        tests.forEach((candidates, target) -> {
            List<List<Integer>> lists = com.combinationSum2(candidates, target);
            List<List<Integer>> list2 = solution.combinationSum2(candidates, target);
            if (list2.size() != lists.size()) {
                System.err.println(lists);
                System.err.println(list2);
            }
            list2.removeAll(lists);
            if (list2.size() != 0) {
                System.out.println(lists + "\t" + list2.size());
                System.out.println(list2 + "\t" + list2.size());
            }
        });
    }
}
